package com.ls.selectSearch;

import java.util.ArrayList;
import java.util.List;

/**
 * 二分查找
 */
public class BinarySearch {
    public static void main(String[] args) {
        // 必须有序数组
        int[] arr = {1,2,3,4,5,6,7,8,9,9,10,11};
//        List<Integer> list = search(arr, 9, 0, arr.length - 1);
//        System.out.println(list);
        System.out.println(search(arr,111,0,arr.length-1));
    }

    /**
     *
     * @param arr 查找数组
     * @param target 目标
     * @param left
     * @param right
     * @return 数组下标
     */
//    public static int search(int[] arr,int target,int left,int right) {
//        int mid = (left + right) >> 1;
//        if (left > right) {
//            return -1;
//        }
//        if (arr[mid] < target) {
//            // 右边找
//            return search(arr, target, mid + 1, right);
//        } else if (arr[mid] > target) {
//            return search(arr, target, left, mid - 1);
//        } else {
//            return mid;
//        }
//    }

    /**
     *  多个相同时每个都找到
     * @param arr
     * @param target
     * @param left
     * @param right
     * @return
     */
    public static List<Integer> search(int[] arr, int target, int left, int right){
        int mid = (left + right)>>1;
        if (left>right){
            ArrayList<Integer> list = new ArrayList<>();
            list.add(-1);
            return list;
        }
        if (arr[mid]<target){
            // 右边找
            return search(arr,target,mid+1,right);
        }else if(arr[mid]>target){
            return search(arr,target,left,mid-1);
        }else {
            // 找到最边上的
            ArrayList<Integer> list = new ArrayList<>();
            int temp = mid;
            while (temp>=0 && arr[temp]==target){
                // 左边
                list.add(temp);
                temp--;
            }
            temp = mid+1;
            while (temp<arr.length && arr[temp]==target){
                // 右边
                list.add(temp);
                temp++;

            }
            return list;

        }

    }
}
